﻿// -----------------------------------------------------------------------
// <copyright file="Selection.cs" company="">
// TODO: Update copyright text.
// </copyright>
// -----------------------------------------------------------------------

namespace DataStructures___Exc1
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    /// <summary>
    /// TODO: Update summary.
    /// </summary>
    public class Selection
    {
        public int Select(int[] i_Array, int i_left, int i_right, int i_nthNumber)
        {
            int pivot;
            int leftPart;

            pivot = Partition(i_Array, i_left, i_right);
            leftPart = pivot - i_left + 1;
            if (i_nthNumber == leftPart)
            {
                return i_Array[pivot];
            }
            if (i_nthNumber < leftPart)
            {
                return Select(i_Array, i_left, pivot - 1, i_nthNumber);
            }
            else
            {
                return Select(i_Array, pivot + 1, i_right, i_nthNumber - leftPart);
            }
        }

        public int IterativeSelect(int[] i_Array, int i_left, int i_right, int i_nthNumber)
        {
            Stack stack = new Stack();
            ItemType curr;
            ItemType next = new ItemType();
            int pivot=0,leftPart,returnValue=0;

            curr = new ItemType(i_left, i_right, i_nthNumber);
            stack.Push(curr);
            while (!stack.IsEmpty())
            {
                curr = stack.Pop();
                pivot = Partition(i_Array, curr.Left , curr.Right);
                leftPart = pivot - curr.Left + 1;
                if (curr.Number < leftPart)
                {
                    next.Left = curr.Left;
                    next.Right = pivot - 1;
                    next.Number = curr.Number;
                    stack.Push(next);
                }
                else if (curr.Number > leftPart)
                {
                    next.Left = pivot + 1;
                    next.Right = curr.Right;
                    next.Number = curr.Number - leftPart;
                    stack.Push(next);
                }
                returnValue = i_Array[pivot];
            }

            return returnValue;
        }

        int Partition(int[] i_array,int i_left, int i_right)
        {
            int pivot = i_array[i_left];
            int i = i_left + 1;
            for (int j = i; j <= i_right; j++)
            {
                if (i_array[j] < pivot)
                {
                    swap(ref i_array[i], ref i_array[j]);
                    i++;
                }
            }
            swap(ref i_array[i_left], ref i_array[i - 1]);
            return i - 1;
        }

        private void swap(ref int first,ref int second)
        {
            int tmp = first;
            first = second;
            second = tmp;
        }
    }
}
